package com.guaoran.interview.in2018.collection.map;

import java.util.HashMap;

/**
 * @author : guaoran
 * @Description : <br/>
 *  参考
 * https://blog.csdn.net/v123411739/article/details/78996181
 * @date :2018/12/23 12:24
 */
public class HashMapDemo {
    public static void main(String[] args) {
        HashMap hashMap = new HashMap();
        for (int i = 0; i < 11; i++) {
            System.out.println(hashMap.put(i + "demo" + i, i));
        }
        //map 如果返回值不是null，说明存在重复值
        System.out.println(hashMap.put(10 + "demo" + 10, 10));
//        hashMap.put("demo2",2);
//        hashMap.put("demo3",3);
//        hashMap.put("demo3",4);
//        hashMap.put("demo4",3);
//        hashMap.put("demo5",3);
//        hashMap.put("demo6",3);
//        hashMap.put("demo7",3);
//        hashMap.put("demo8",3);
//        hashMap.put("demo9",3);
//        hashMap.put("demo10",3);
//        hashMap.put("demo11",3);
//        hashMap.put("demo12",3);
//        hashMap.put("demo13",3);
//        hashMap.put("demo14",3);
//        int hashCode = "demo".hashCode();
//        System.out.println(Integer.toBinaryString(hashCode));
//        System.out.println(Integer.toBinaryString(hashCode>>>16));
//        System.out.println(Integer.toBinaryString(hashCode^hashCode>>>16));
    }

    /**
     * HashMap 的内部数据结构:基于数组+链表（单向）
     *
     *  transient Node<K,V>[] table;
     *
     //数组的默认大小是16
     *  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

     //扩容因子
     * //The load factor used when none specified in constructor.
     *  static final float DEFAULT_LOAD_FACTOR = 0.75f;

     //当数组下的链表节点超过这个数的时候，转换成红黑树
     *  static final int TREEIFY_THRESHOLD = 8;
     *
     //存放 数据的对象
     *  static class Node<K,V>  implements Map.Entry<K,V>
     *      final int hash;
     *      final K key;
     *      V value;
     *      Node<K,V> next;
     *
     */

    /*
        HashMap对象的key、value值均可为null。
        hash 算法的作用就是为了Node节点落点的一个浅析计算
        hash 算法：key.hashCode ^ key.hashCode 的高16位
            static final int hash(Object key) {
                //获得key的hashCode值，
                //获得哈市Code的高16位，
                //进行^ 异或操作
                int h;
                return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
            }

    */
    /*
        put 的过程
            1.通过hash算法根据key获得一个hash 即 hash（key）
            2.如果数组为空，则进行初始化数组
            n = (tab = resize()).length;
                //resize():
                newCap = DEFAULT_INITIAL_CAPACITY;//1 << 4 // aka 16
                // DEFAULT_LOAD_FACTOR = 0.75f; 扩容因子
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            3.判断key最终会落到数组的哪个节点下，如果该位置为空，则进行保存
                //根据数组的长度-1 与（&） 上 hash算法的结果，
                //最终能获得一个位于[0-15]或[0-数组.lenth-1]的值，即节点的下标位置
                if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
                (hash %16 和hash & 15 得到的结果是相同的，为什么要采用 & 的操作)
                    因为& 的操作效率比较高
            4.判断key最终会落到数组的哪个节点下，如果该位置不为空
                1.如果key值相同则进行覆盖
                2.如果key值不相同
                    1.采用红黑树的方式
                         else if (p instanceof TreeNode)
                            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

                    2.采用链表的方式，会依次遍历该及节点链表中的节点是否为空，如果不为空则保存到节点的下个节点中
                        即 node.next  = p (: p = tab[i = (n - 1) & hash]))
                        p.next = newNode(hash, key, value, null);
                        //如果该节点下的链表节点的长度大于等于8 //TREEIFY_THRESHOLD = 8;
                        //binCount 从0开始遍历的
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //转换成红黑树，类似二叉树
                            treeifyBin(tab, hash);


            5.保存完节点之后，进行判断是否需要扩容
                数组某节点下的链表的节点是数的大小超过8的时候，会进行转换成红黑树，
                那么如果数组的节点呢? 当map的长度超过数组的长度*0.75的时候，会进行扩容，扩容成数组长度16 <<1  再次扩容的时候就是 16*0.75<< 1
                ++modCount;
                //threshold = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
                if (++size > threshold)
                    resize();



     */
}
